#include "test_for_twosum.h"
#include <math.h>
#include <stdio.h>

int xtest_case1[] = {50,7,11,105};
int xtest_case2[] = {3,2,4};
int xtest_case3[] = {3,3};

int max_prime = 1;

int get_maxprime(int prime)
{
    int x_max_prime = 1;
    for(int i = 1; i < prime; i++)
    {
        for(int j = 2; j <= i; j++)
        {
            if((i % j == 0) && (i != j))
            {
                break;
            }
            else if((i % j == 0) && (i == j))
            {
                if(i > x_max_prime)
                {
                    x_max_prime = i;
                }
            }
        }
    }
    return x_max_prime;
}

hash_t** create_hash(int prime_n)
{
    hash_t** ret = (hash_t** )malloc(prime_n * sizeof(hash_t));
    for(int i = 0; i < prime_n; i++)
    {
        ret[i] = (hash_t* )malloc(sizeof(hash_t));
        ret[i]->data = -1;
        ret[i]->next = NULL;
    }
    return ret;
}

void insert_hash_table(hash_t** phash, int data)
{
    int key = abs(data) % max_prime;
    hash_t* phead = phash[key];
    hash_t* pnew = (hash_t* )malloc(sizeof(hash_t));
    pnew->data = data;
    pnew->next = phead->next;
    phead->next = pnew;
    // pnew->next = phead;
    // phead = pnew;
}

int search_hash_table(hash_t** phash, int data)
{
    int key = abs(data) % max_prime;
    hash_t* phead = phash[key];
    while(phead->next != NULL)
    {
        if(phead->data == data)
        {
            return 1;
        }
        phead = phead->next;
    }

    if(phead != NULL && phead->next == NULL) //只有一个节点的情况
    {
        if(phead->data == data)
        {
            return 1;
        }
    }
    return 0;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* nums_ret = (int* )malloc(sizeof(int) * 2);
    hash_t** phash_x = NULL;
    max_prime = get_maxprime(numsSize); //获取hash表元素个数
    phash_x = create_hash(max_prime);
    for(int i = 0; i < numsSize; i++)
    {
        insert_hash_table(phash_x, target - nums[i]);
    }
    for(int i = 0, j = 0; i < numsSize; i++)
    {
        if(search_hash_table(phash_x, nums[i]) == 1)
        {
            nums_ret[j++] = i;
        }
        if(j == 2)
        {
            *returnSize = 2;
            return nums_ret;
        }
    }
    *returnSize = 0;
    return NULL;
}

void test_for_twosum(void)
{
    int ret_size[2] = {0};
    int ret_num[2] = {0};
    int* pret = ret_num;
    pret = twoSum(xtest_case1, 4, 155, ret_size);
    printf("[%d,%d]\n", pret[0], pret[1]);
}